import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName Offer34
 * @Description 剑指 Offer 34. 二叉树中和为某一值的路径
 * @Author clockTown
 * @Date 2021/8/26 21:52
 * @Version 1.0
 */
class Offer34 {
}


class Offer34V0 {

    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return res;
    }

    private void dfs(TreeNode root, int target) {
        /**
         * target<0的条件不能加，否则会无法通过测试
         [-2,null,-3]
         -5
         */
        if (target < 0 || root == null) {
            return;
        }
        list.add(root.val);
        target = target - root.val;
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new LinkedList<>(list));
        }
        dfs(root.left, target);
        dfs(root.right, target);
        list.removeLast();
    }
}